package com.peng.leetcode.array;

import java.util.ArrayList;
import java.util.List;

/**
 * Subsets
 * <p>
 * 子集问题， 使用回溯算法求解。 每个元素分为选择和不选择
 *
 * @author: lupeng6
 * @create: 2021/3/31 11:09
 */
public class Subsets {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};

        System.out.println(new Subsets().subsets(nums));
    }

    private List<List<Integer>> answer;

    private int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }

        answer = new ArrayList<>();
        this.nums = nums;
        dfs(0, new ArrayList<>());
        return answer;
    }

    private void dfs(int index, List<Integer> list) {
        if (index == nums.length) {
            answer.add(new ArrayList<>(list));
            return;
        }

        list.add(nums[index]);
        dfs(index + 1, list);


        list.remove(list.size() - 1);
        dfs(index + 1, list);
    }


}
